package com.leetcode.蓝桥杯.十一届国赛;

import java.util.Arrays;

/**
 * 在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
例如，在字符串lanqiao中，如果取出字符n和q，则 nq组成一个单调递增子序列。类似的单调递增子序列还有lnq、i、ano等等。小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到ao，取最后两个字符也可以取到ao。小蓝认为他们并没有本质不同。
对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个?例如，对于字符串lanqiao，本质不同的递增子序列有21个。它们分别是l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。
请问对于以下字符串(共200个小写英文字)∶
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个?

思路：动态规划。dp[i]以i为结尾的递增子序列有多少个。
 * 求dp[i]: 1、在前面的以1~(i-1)为结尾的递增子序列中，如果str.charAt(i) > str.charAt(j)，那么dp[i] += dp[j]。
 * 2、去重。如果str.charAt(i) == str.charAt(j)，说明j之前以j为结尾的递增子序列 和 j之前以i为结尾的子序列是相同的，
 * 因此，到这里就可以不用再继续往前计算了，并且由于dp初始都是1，所以单个字符，j结尾和i结尾重复了一个，需要减1:dp[i]--
 * 
 * 
 * @author LZF
 *
 */
public class 填空题4 {	
	public static void main(String[] args) {
		String str = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf" + 
				"iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij" + 
				"gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad" + 
				"vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
		int N = str.length();
		long[] dp = new long[N];
		Arrays.fill(dp,1);
		for(int i = 0;i < N;i++) {
			for(int j = i - 1;j >= 0;j--) {//必须是从后往前遍历！！！！！！才能避免重复的
				if(str.charAt(i) > str.charAt(j)) {
					dp[i] += dp[j];
				}
				else if(str.charAt(i) == str.charAt(j)) {
					dp[i]--;//减去单个字符重复的
					break;
				}
			}
		}
		long ans = 0;
		for(int i = 0;i < dp.length;i++) {
			ans += dp[i];
		}
		System.out.println(ans);
	}

}
